package buaa.qel.rpc.test.functions;

/**
 * N皇后问题超级优化，时间复杂度O（N^N），但是常数非常优秀
 */
public class NQueen_BitCal {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(NQueen(14));
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }

    public static int NQueen(int n){
        if(n < 1 || n > 16) return -1;
        int limit = (1 << n)-1;
        return process(limit,0,0,0);
    }

    public static int process(int limit,int colLim,int leftLim,int rightLim){
        if(colLim == limit){
            return 1;
        }
        int pos = limit & (~(colLim | leftLim | rightLim));
        int rightOne = 0;
        int res = 0;
        while(pos != 0){
            rightOne = pos & ((~pos)+1);
            pos -= rightOne;
            res += process(limit,(colLim | rightOne),(leftLim | rightOne) << 1 , (rightLim | rightOne) >>> 1);
        }
        return res;
    }
}
